package LeetCode.leetcode;

import domain.TreeNode;

import java.util.Stack;

/**
 * @Auther: leiwenkang
 * @Date: 2020/8/23 21:47
 * @Description:
 */
public class Test98验证二叉搜索树 {
    public static void main(String[] args) {
        TreeNode root = new TreeNode(2);
        TreeNode node1 = new TreeNode(1);
        TreeNode node2 = new TreeNode(3);

        root.left = node1;
        root.right = node2;

        System.out.println(new Test98验证二叉搜索树().isValidBST(root));
    }
    //中序遍历，遍历结果是否从小到大排列
    public boolean isValidBST(TreeNode root) {
        Stack<TreeNode> stack = new Stack<>();
        double lastVal = -Double.MAX_VALUE;

        while (root != null || !stack.isEmpty()) {
            while (root != null) {
                stack.push(root);
                root = root.left;
            }

            if (!stack.isEmpty()) {
                root = stack.pop();
                if (root.val <= lastVal) {
                    return false;
                }
                lastVal = root.val;
                root = root.right;
            }
        }
        return true;
    }
}